/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/9 21:44
 */
// 在排序数组中查找元素的第一个和最后一个位置
    // https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
public class Solution34 {
    public int[] searchRange(int[] nums, int target) {
        // 找左右边界
        // 当 lower 为 true 时，该方法用于查找左边界（即目标值第一次出现的位置）。如果 nums[mid] == target，它不会立即停止，
            // 而是继续向左查找，直到找到一个比 target 小的数或者到达数组的左边界。
        //当 lower 为 false 时，由于最终返回的是 ans - 1，所以实际上是在查找右边界（即目标值最后一次出现的位置的下一个位置的前一个位置）。
            // 这听起来有点绕，但实际上是有效的，因为 ans 最终会指向 target 最后一次出现的位置或者比它大的第一个数的位置，通过减一就得到了 target 的右边界。
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        // 判断合法性
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    private int binarySearch(int[] nums, int target, boolean flag) {
        // 二分查找
        int left = 0, right = nums.length - 1;
        // 返回索引
        int ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            // 如果在左边或者找的左边界
            if (nums[mid] > target || (flag && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
